11271. Sum of squares Cnk

 

Given a non-negative integer n, find the sum of binomial coefficients

 

Input. One non-negative integer n (n ≤ 60).

 

Output. Print the value of the sum.

 

Sample input

Sample output

3

20

 

 

SOLUTION

combinatorics

 

Algorithm analysis

Let’s consider 2n objects a1, …, a2n and find the number of ways to select n objects out of 2n.

We’ll divide the set in half: {a1, a2, …, an, an+1, …, a2n}. To choose n objects from 2n, we’ll select k (k ≤ n) objects from the left half (from the set {a1, a2, …, an}) and n – k objects from the right half (from the set {an+1, an+2, …, a2n}). The number of ways to make such a selection, according to the rule of multiplication, is equal to  = . Since k can take values from 0 to n,  is equal to the number of ways to choose n objects from 2n, which is equal to . Thus,

 =

 

Example

For n = 3 the answer is  = 12 + 32 + 32 + 12 = 20.

At the same time  =  =  = 20.

 

Algorithm realization

The Cnk function computes the value of the binomial coefficient .

 

long long Cnk(long long n, long long k)

{

  long long res = 1;

  if (k > n - k) k = n - k;

  for (long long i = 1; i <= k; i++)

    res = res * (n - i + 1) / i;

  return res;

}

 

The main part of the program. Read the value of n.

 

scanf("%lld", &n);

 

Compute and print the answer.

 

res = Cnk(2*n, n);

printf("%lld\n", res);

 

Java realization

 

import java.util.*;

 

public class Main

{

  public static long Cnk(long n, long k)

  {

    long res = 1;

    if (k > n - k) k = n - k;

    for (long i = 1; i <= k; i++)

     res = res * (n - i + 1) / i;

    return res;

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    long n = con.nextLong();

    long res = Cnk(2*n, n);

    System.out.println(res);

    con.close();

  }

}

 

Python realization

The function Cnk computes the value of the binomial coefficient .

 

def Cnk(n, k):

   res = 1

   if k > n - k: k = n – k

   for i in range(1, k+1):

     res = res * (n - i + 1) // i

   return res

 

The main part of the program. Read the value of n.

 

n = int(input())

 

Compute and print the answer.

 

res = Cnk(2 * n, n)

print(res)

 

Python realization – comb

Read the value of n.

 

n = int(input())

 

Compute and print the answer.

 

res = math.comb(2 * n, n)

print(res)